package javatest.collections;

import java.util.Stack;


public class ListHelper {
    
    /* 按数组创建一个单链表无环 */
    public static Node ceateList(int[] values) {
        if (values.length == 0) return null;
        Node head = new Node(values[0]);
        Node prev = head;
        for (int i = 1; i < values.length; i++) {
            Node current = new Node(values[i]);
            prev.next = current;
            prev = current;
        }
        return head;
    }

    /* 是否是回文链表 */
    public static boolean isPalindrome(Node head){
        if (head == null) return false;
        Stack<Node> s = new Stack<>();   
        s.push(head);
        Node prev = head;
        while(prev.next != null) {
            s.push(prev.next);
            prev = prev.next;
        }
        while (s.pop().value == head.value) {
            head = head.next;
            if (head == null) return true;
        }
        return false;
    }

    /* 快慢指针法求证链表是否有环 */
    public static boolean isRing(Node head){
        if (head == null || head.next == null || head.next.next == null) return false;
        Node slow = head.next;
        Node fast = slow.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast){
                return true;
            }
        }
        return false;
    }
    /* 获取入环节点在链表中的索引 */
    public static int ringFirstIndex(Node head){
        if (head != null && head.next != null && head.next.next != null) {
            Node slow = head.next;
            Node fast = slow.next;
            boolean isRing = false;
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast){
                    isRing = true;
                    break;
                }
            }
            Node ringFirstNode = null;
            if (isRing){
                fast = head;
                while (fast.next != null && fast.next.next != null) {
                    slow = slow.next;
                    fast = fast.next;
                    if (slow == fast) {
                        ringFirstNode = slow;
                        break;
                    }
                }
                fast = head;
                int index = 0;
                while (fast.next != null){
                    if (ringFirstNode == fast) {
                        return index;
                    }
                    fast = fast.next;
                    index ++;
                }
            }
        }
        return -1;
    }
}
